package com.sicheng.蓝桥.国赛准备.第十一届蓝桥杯JAVAB;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/10 20:19
 */
public class E玩具蛇 {
    /**
     * 小蓝有一条玩具蛇，一共有 16  节，上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 9090 度角。
     * 小蓝还有一个 4×4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母 A  到 P  共 16  个字母。
     * 小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。
     * 原文链接：https://blog.csdn.net/qq_43449564/article/details/109703534
     */


    public static void main(String[] args) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = 1;
                dfs(i, j);
                g[i][j] = 0;
            }
        }

        System.out.println(count);
    }

    static int n = 4;
    static int[][] d = {
            {0, 1}, {1, 0}, {-1, 0}, {0, -1}
    };
    static int[][] g = new int[n][n];

    static long count = 0;

    static void dfs(int i, int j) {
        if (g[i][j] == n * n) {
            count++;
            return;
        }

        for (int[] ints : d) {
            int x = i + ints[0];
            int y = j + ints[1];
            if (x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 0) {
                g[x][y] = g[i][j] + 1;
                dfs(x, y);
                g[x][y] = 0;
            }
        }
    }
}
